// GFG_Trees.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "NodeDefs.h"
#include <vector>
#include <list>

void printPreorder(BinTreeNode* node)
{   
    if(node == NULL)
        return;
    printf("%d ", node->data);
    printPreorder(node->left);
    printPreorder(node->right);
}
void printInorder(BinTreeNode* node)
{   
    if(node == NULL)
        return;
    printInorder(node->left);
    printf("%d ", node->data);    
    printInorder(node->right);
}
void printPostorder(BinTreeNode* node)
{
    if(node == NULL)
        return;
    printPostorder(node->left);    
    printPostorder(node->right);
    printf("%d ", node->data);    
}

void GetPreorder(BinTreeNode* node, std::vector<int> &Arr)
{   
    if(node == NULL)
        return;
    Arr.push_back(node->data);    
    GetPreorder(node->left, Arr);
    GetPreorder(node->right, Arr);
}
void GetInorder(BinTreeNode* node, std::vector<int> &Arr)
{   
    if(node == NULL)
        return;
    GetInorder(node->left, Arr);
    Arr.push_back(node->data);    
    GetInorder(node->right, Arr);
}
void GetPostorder(BinTreeNode* node, std::vector<int> &Arr)
{
    if(node == NULL)
        return;
    GetPostorder(node->left, Arr);    
    GetPostorder(node->right, Arr);
    Arr.push_back(node->data);    
}


void DeleteBinTree(BinTreeNode* root)
{
    if(root == NULL)
        return;

    //Delete must be done by Post order
    DeleteBinTree(root->left);
    DeleteBinTree(root->right);
    if(root)
        delete root;
    root = NULL;
}

long SizeBinTree(BinTreeNode* root)
{
    if(root == NULL)
        return 0;
    return SizeBinTree(root->left) + SizeBinTree(root->right) + 1;
}

bool identicalTrees(BinTreeNode* a, BinTreeNode* b)
{
    bool identical = false;
    if(a == NULL && b == NULL)
        identical = true;
    else if(a != NULL && b != NULL)
    {
        if(a->data == b->data)
        {
            identical = identicalTrees(a->left, b->left) && identicalTrees(a->right, b->right);
        }
    }
    return identical;
}

int maxDepth(BinTreeNode* node) 
{   
    int depth = 0;
    if(node != NULL)        
    {
        int lDepth = maxDepth(node->left);
        int rDepth = maxDepth(node->right);
        depth = ((lDepth > rDepth) ? lDepth : rDepth) + 1;                
    }
    return depth;
}

void mirror(BinTreeNode* node)
{
    //Pre order or post order does not matter, swap and recurse or recurse and swap
    if(node != NULL)
    {   
        BinTreeNode* pLeftNode = node->left;
        node->left = node->right;
        node->right = pLeftNode;

        mirror(node->left);
        mirror(node->right);
    }    
}


void printPathHelper(BinTreeNode* root, std::list<int> &printPathList)
{
    if(root == NULL)
        return;

    printPathList.push_back(root->data);        // simulate stack, kind of pre order
    printPathHelper(root->left, printPathList);            
    printPathHelper(root->right, printPathList);
    
    // Kind of post order
    if(root->left == NULL && root->right == NULL)
    {   
        if(printPathList.size())
        {
            printf("\n");
            for(auto it = printPathList.begin(); it != printPathList.end(); it++)        
                printf("%d ", (*it));        
            printf("\n");
        }              
    }
    printPathList.pop_back();       
}
void printPath(BinTreeNode* root)
{
    std::list<int> printPathList;
    printPathHelper(root, printPathList);
    printPathList.clear();
}

BinTreeNode* lca(BinTreeNode* root, int n1, int n2)
{
	return NULL;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //BinTreeNode *root  = NewNode(1);
    //root->left             = NewNode(2);
    //root->right           = NewNode(3);
    //root->left->left     = NewNode(4);
    //root->left->right   = NewNode(5);     
    //
    //printf("\n Size of the binary tree is %d \n", SizeBinTree(root));    

    //printf("Height of tree is %d", maxDepth(root));

    ///*printf("\n Preorder traversal of binary tree is \n");
    //printPreorder(root);*/

    //printf("\n Inorder traversal of binary tree is \n");
    //printInorder(root);  

    //mirror(root);

    //printf("\n Inorder traversal of binary tree is \n");
    //printInorder(root);  

    //printf("\n Postorder traversal of binary tree is \n");
    //printPostorder(root);

    //DeleteBinTree(root);

    /*BinTreeNode *root1 = NewNode(1);
    BinTreeNode *root2 = NewNode(1);
    root1->left = NewNode(2);
    root1->right = NewNode(3);
    root1->left->left  = NewNode(4);
    root1->left->right = NewNode(5); 
 
    root2->left = NewNode(2);
    root2->right = NewNode(3);
    root2->left->left = NewNode(4);
    root2->left->right = NewNode(5); 

    if(identicalTrees(root1, root2))
        printf("Both tree are identical.");
    else
        printf("Trees are not identical.");*/

    BinTreeNode *root  = NewNode(1);
    root->left = NewNode(2);
    root->left->left     = NewNode(4);
    root->left->left->left = NewNode(8);
    root->left->left->right = NewNode(9);
    root->left->right   = NewNode(5);     
    root->left->right->left = NewNode(10);     
    root->left->right->left->left = NewNode(16);     
    root->left->right->left->right = NewNode(17);     
    root->left->right->right = NewNode(11);     

    root->right = NewNode(3);
    root->right->left     = NewNode(6);
    root->right->left->left = NewNode(12);
    root->right->left->right = NewNode(13);
    root->right->right   = NewNode(7);     
    root->right->right->left = NewNode(14);     
    root->right->right->left->left = NewNode(18);     
    root->right->right->left->right = NewNode(19);     
    root->right->right->right = NewNode(15);     
    root->right->right->right->left = NewNode(20);     

    printf("\n Size of the binary tree is %d \n", SizeBinTree(root));    

    printf("Height of tree is %d", maxDepth(root));

    printf("\n Preorder traversal of binary tree is \n");
    printPreorder(root);

    printf("\n Inorder traversal of binary tree is \n");
    printInorder(root);  

    printf("\n Postorder traversal of binary tree is \n");
    printPostorder(root);

    printPath(root);

    /*std::vector<int> preOrderList;
    GetPreorder(root, preOrderList); 
    printf("\n Preorder traversal of binary tree from list \n");
    for(std::vector<int>::iterator it = preOrderList.begin(); it != preOrderList.end(); it++)    
        printf("%d ", (*it));    
    
    std::vector<int> inOrderList;
    GetInorder(root, inOrderList); 
    printf("\n Inorder traversal of binary tree from list \n");
    for(std::vector<int>::iterator it = inOrderList.begin(); it != inOrderList.end(); it++)    
        printf("%d ", (*it));    

    std::vector<int> postOrderList;
    GetPostorder(root, postOrderList); 
    printf("\n Postorder traversal of binary tree from list \n");
    for(std::vector<int>::iterator it = postOrderList.begin(); it != postOrderList.end(); it++)    
        printf("%d ", (*it));*/



    getchar();
	return 0;
}

